1. Field of the Invention:
The method and apparatus of the present invention relates to dithering techniques used to represent digital images. More particularly, the method and apparatus of the present invention relates to rendering dithered vectors.
2. Related Applications
The present invention is related to U.S. patent application Ser. No. 07/413,991, filed Sep. 28, 1989 entitled "Method and Apparatus For Non-Linear Dithering of Graphic Images, U.S. patent application Ser. No. 07/413,977, filed Sep. 28, 1989 entitled "Method and Apparatus For The Dithering of Antialiased Vectors" and U.S. patent application, Ser. No. 07/413,983, filed Sep. 28, 1989 entitled "Method and Apparatus for Dithering Graphic Images" and are herein incorporated by reference.
3. Art Background:
A picture or image may be thought of as a continuous representation of the object projected. It is often desirable to represent images on a digital computer display device such as a monitor or a printer. However, a computer and its output devices are binary in nature. A computer display comprises a grid of display elements, referred to as pixels, which can either be in one of a plurality of on states indicative of its intensity, in which the pixel location is illuminated, or in the off state in which the pixel location is not illuminated. In order to display continuous images, the continuous images must be converted to discrete representations corresponding to the pixel locations on the display device. A digital image is quantized in both the spatial domain and the intensity domain.
The amount of memory available dictates the quantized levels available to represent the image. If the resolution of either sample space (i.e. spatial and intensity) drops below a threshold (due to memory limitations), the eye will detect the discrete boundaries between samples. In the intensity domain, insufficient resolution is marked by the presence of artificial edges delimiting the transitions between regions of incremental intensity. Other undesirable visible effects, such as patterning, color shifting and biasing, are introduced due to the visible thresholding between quantized intensity levels.
To minimize the undesirable effects, a technique, referred to as dithering or digital halftoning, is used. Dithering is a technique which permits the simulation of intensity levels between quantized levels by permitting the eye to integrate fine detail within an area and record only the overall intensity of the area. Dithering aims to sacrifice some of an image's spatial resolution for an increase in perceived intensity resolution, accomplished by averaging the intensities of several neighboring pixels to simulate intensities that lie between quantization levels. Typically, this technique works well, since the eye naturally blends individual pixel values such that only the average intensity in the surrounding area or neighborhood is perceived. For more information on dithering, see Ulichney, Digital Halftoning (1987, MIT Press); Foley & Van Dam, Fundamentals of Interactive Computer Graphics, p. 597-602 (Addison-Wesley, 1984).
Several types of dithering techniques exist. The types of dithering algorithms are distinguished by the way the neighborhoods are chosen. In the technique of ordered dither, the neighborhoods are chosen according to a two dimensional set of values, referred to as the dither table or dither matrix, which is tiled into the image's coordinate space. Typically for area dither, the table has the same number of row and column elements and the total number of entries in the table equals the number of simulatable intensity levels between the quantized levels. The values contained in the table are used to make decisions about which quantized intensity value will be output at each position, that is, should the intensity value be quantized to the quantized value above or below the original intensity value. Typically, the dither table values are different at each x,y coordinate location such that when a constant input intensity is dithered over some area, the output values will alternate in some pattern between the upper and lower quantized intensity levels.
The ordered dither process is explained in reference to FIG. 1a. Process 1.0 determines the appropriate index into the dither matrix based on the x-y coordinates of the current pixel. Conceptually, the idea is to "tile" the dither matrix into the image coordinate space, thereby replicating each entry once every n pixels, where n is the dimension of the dither table. The indices to the matrix, i-j, are determined according to the following equations: EQU i=x mod n EQU j=y mod n
If n is a power of two, it is possible to utilize the least significant bits of the x-y screen coordinates for indexing the dither matrix. For example, if the dimension of the dither matrix is 4.times.4, then the 2 least significant bits of the x-y coordinates will provide the required modulo-4 indexing.
At process 2.0, the dither values are retrieved from the matrix according to i-j dither indices determined. By the nature of the problem, the output intensity scale has fewer entries than the input intensity scale. In order to quantize the input value, there must be a predetermined correspondence between each level on the output scale to a value on the input scale. It is the task of process 3.0 to determine the input-scale base value which is the value from the input scale which is nearest to but not greater than the original input intensity or and which directly corresponds to a value in the stored range of intensities.
The next process, 4.0, determines the value in the stored range of quantized intensity levels that corresponds to the input - scale base. This value will be referred to as the "stored range base value".
At process 5.0, the difference between the input intensity value and its input-scale base value is determined. The resoft, always guaranteed to be greater than or equal to zero, is the delta value passed along to process 6.0. Process 6.0 is the pivotal dither process, comparing the delta value to the dither value and outpuffing either the stored range base value or the next higher value. Specifically, if the delta value is less than or equal to the dither value, the stored range base value is output; if delta is greater than the dither value, then the stored range base plus one is output. The output from process 6.0 is the quantized pixel value that is deposited into the pixel store (e.g. a frame buffer).
Although quantized values are stored, these values are typically mapped back to an intensity scale with a greater intensity range for display viewing. That is the task of process 7.0, which is usually implemented by lookup-tables lying between the frame buffer output and the video display input. (This is not part of dithering per se, but is utilized for reconstruction of the dithered image for viewing.)
By performing processes 1.0 through 6.0 on successive input values, dithering causes values both greater than and less than the input intensity to ultimately be displayed, producing regions over which the overall average intensity is approximately equal to the original input intensity.
The dithering process is applied to all portions of the digital image. Although dithering works well when operating on areas of pixels, dithering does not work well with vectors because the area of a vector is small and dithering relies on the integration of several pixels over a sizeable area in order to convey the desired intermediate intensity. Further, when a square dither matrix is aligned with the screen, the dispersion of dither values varies with the angle of the vector with respect to the screen. This latter property of a screen aligned dither matrix is not desirable and the dither process should be vector angle independent.
This is best illustrated by FIG. 1b which shows two dithered vectors of single pixel width (Vector 1 and Vector 2). Review of the intensity values of the vector 1 particularly points out the problem. The vector consists of high dither values and not an alternating pattern of low dither/high dither values which is desirable to represent intermediate intensity values. A desirable configuration of intensity values is illustrated in FIG. 1c.